package com.gaogzhen.datastructure.queue;

import java.io.Serializable;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * @author Administrator
 * @date 2022-12-09 20:24
 */
public class IndexPriorityQueue<E extends Comparable<E>> implements Queue<E>, Serializable {

    /**
     * 存放元素数组
     */
    private final E[] table;

    /**
     * 堆排序数组
     */
    private final int[] pq;

    /**
     * 数组pq的逆数组
     */
    private final int[] qp;

    /**
     * 元素个数
     */
    private int size;

    /**
     * 最大元素个数
     */
    private final int maxSize;

    /**
     * 比较器，默认从小到大排序
     */
    private Comparator<E> comparator;

    /**
     * 是否是最大索引队列，默认不是即最小优先队列
     */
    private boolean max = false;


    /**
     * 传从小到大排序，max指定false；从大到小排序，指定max为true
     */
    public IndexPriorityQueue(int maxSize, Comparator<E> comparator, boolean max) {
        this(maxSize);
        if (comparator != null) {
            this.comparator = comparator;
        }
        this.max = max;
    }

    public IndexPriorityQueue(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException();
        }
        this.maxSize = maxSize;
        size = 0;

        table = (E[]) new Comparable[maxSize];
        pq = new int[maxSize + 1];
        qp = new int[maxSize];
        for (int i = 0; i < maxSize; i++) {
            qp[i] = -1;
        }
        this.comparator = Comparable::compareTo;
    }

    /**
     * 插入元素
     *
     * @param e 元素
     */
    @Override
    public void offer(E e) {
        throw new UnsupportedOperationException();
    }

    /**
     * 插入元素
     *
     * @param i 索引i
     * @param e 元素e
     */
    public void insert(int i, E e) {
        validateIndex(i);
        if (contains(i)) {
            throw new IllegalArgumentException("索引已经存在");
        }
        if (size >= maxSize) {
            throw new IllegalArgumentException("队列已满");
        }
        size++;
        table[i] = e;
        pq[size] = i;
        qp[i] = size;
        swim(size);
    }

    /**
     * 获取队首元素
     *
     * @return 队首元素
     */
    @Override
    public E peek() {
        validateEmpty();
        return table[pq[1]];
    }

    private void validateEmpty() {
        if (size == 0) {
            throw new NoSuchElementException();
        }
    }

    /**
     * 获取并删除堆有序队首元素
     *
     * @return 队首元素
     */
    @Override
    public E poll() {
        validateEmpty();
        int m = pq[1];
        E oldVal = table[m];
        exch(1, size--);
        sink(1);
        qp[m] = -1;
        table[m] = null;
        pq[size + 1] = -1;
        return oldVal;
    }

    /**
     * 判断队列是否为空
     *
     * @return {@code true}队列为空;反之{@code false}
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回元素个数
     *
     * @return 元素个数
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 更换索引i处元素为e
     *
     * @param i 索引
     * @param e 更换后的值
     */
    public E changeVal(int i, E e) {
        validateIndex(i);
        if (!contains(i)) {
            throw new NoSuchElementException("队列不存在该索引：" + i);
        }
        E o = table[i];
        table[i] = e;
        int j = qp[i];
        swim(j);
        sink(j);
        return o;
    }


    /**
     * 索引i处优先级降级为e
     *
     * @param i 索引
     * @param e 目标值
     */
    public void decreaseVal(int i, E e) {
        validateIndex(i);
        if (!contains(i)) {
            throw new NoSuchElementException("队列不存在该索引：" + i);
        }
        if (table[i].compareTo(e) == 0) {
            throw new IllegalArgumentException(e + " 优先级不能等于 " + table[i]);
        }
        if (table[i].compareTo(e) < 0) {
            throw new IllegalArgumentException(e + " 优先级不能高于原优先级 " + table[i]);
        }
        table[i] = e;
        if (max) {
            sink(qp[i]);
        } else {
            swim(qp[i]);
        }
    }

    /**
     * 索引i处元素优先级升级为e
     *
     * @param i 索引i
     * @param e 目标值
     */
    public void increaseVal(int i, E e) {
        validateIndex(i);
        if (!contains(i)) {
            throw new NoSuchElementException("队列不存在该索引：" + i);
        }
        if (table[i].compareTo(e) == 0) {
            throw new IllegalArgumentException(e + " 优先级不能等于 " + table[i]);
        }
        if (table[i].compareTo(e) > 0) {
            throw new IllegalArgumentException(e + " 优先级不能低于原优先级 " + table[i]);
        }
        table[i] = e;
        table[i] = e;
        if (max) {
            swim(qp[i]);
        } else {
            sink(qp[i]);
        }
    }

    /**
     * 判断索引是否已经存在
     *
     * @param i 元素索引
     * @return {@code true}逆数组包含该索引;反之{@code false}
     */
    public boolean contains(int i) {
        validateIndex(i);
        return qp[i] != -1;
    }

    /**
     * 删除索引i处的元素
     *
     * @param i 索引i
     * @return 删除的元素
     */
    public E delete(int i) {
        validateIndex(i);
        if (!contains(i)) {
            throw new NoSuchElementException("队列不存在该索引: " + i);
        }
        int k = qp[i];
        exch(k, size--);
        swim(k);
        sink(k);
        E o = table[k];
        table[k] = null;
        qp[k] = -1;
        pq[size + 1] = -1;
        return o;
    }

    /**
     * 交换元素
     *
     * @param i 索引i
     * @param j 索引j
     */
    private void exch(int i, int j) {
        int p = pq[i];
        pq[i] = pq[j];
        pq[j] = p;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }

    /**
     * 比较索引i和索引j处的值
     *
     * @param i
     * @param j
     * @return
     */
    private boolean compare(int i, int j) {
        return comparator.compare(table[pq[i]], table[pq[j]]) < 0;
    }

    /**
     * 返回索引i处的值
     *
     * @param i 索引
     * @return i处的值
     */
    public E valueOf(int i) {
        validateIndex(i);
        if (!contains(i)) {
            throw new NoSuchElementException("索引不在优先队列中");
        }
        return table[i];
    }

    /**
     * 返回最低(高)优先级元素对应的索引
     *
     * @return 最低(高)优先级元素对应的索引
     */
    public int firstIndex() {
        validateEmpty();
        return pq[1];
    }

    /**
     * 下沉
     *
     * @param i 下沉起始索引
     */
    public void sink(int i) {
        while (2 * i <= size) {
            int j = 2 * i;
            if (j < size && compare(j + 1, j)) {
                j++;
            }
            if (!compare(j, i)) {
                break;
            }
            exch(i, j);
            i = j;
        }
    }

    /**
     * 上浮
     *
     * @param i 起始索引
     */
    public void swim(int i) {
        while (i > 1 && compare(i, i / 2)) {
            exch(i, i / 2);
            i /= 2;
        }
    }

    /**
     * 校验索引i
     *
     * @param i 索引i
     */
    private void validateIndex(int i) {
        if (i < 0) {
            throw new IllegalArgumentException("index is negative: " + i);
        }
        if (i >= maxSize) {
            throw new IllegalArgumentException("index >= capacity: " + i);
        }
    }

    @Override
    public String toString() {
        Iterator<E> iterator = iterator();
        if (!iterator.hasNext())
            return "[]";
        StringBuilder b = new StringBuilder("[");
        while (true) {
            E next = iterator.next();
            b.append(next);
            if (!iterator.hasNext()) {
                return b.append("]").toString();
            }
            b.append(",");
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new Itr();
    }

    private class Itr implements Iterator<E> {
        // create a new pq
        private IndexPriorityQueue<E> copy;

        public Itr() {
            copy = new IndexPriorityQueue<E>(maxSize, comparator, max);
            for (int i = 1; i <= size; i++) {
                copy.insert(pq[i], table[pq[i]]);
            }
        }

        @Override
        public boolean hasNext() {
            return !copy.isEmpty();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }

        @Override
        public E next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            return copy.poll();
        }
    }
}
